#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//class Solution {
//public:
//    void moveZeroes(vector<int>& nums) {
//        int n = nums.size();
//        int slow = 0;
//        int fast = 0;
//        for (; fast < n; fast++)
//        {
//            if (nums[fast])
//            {
//                swap(nums[slow++], nums[fast]);
//            }
//        }
//    }
//};
//
//class Solution {
//public:
//    void duplicateZeros(vector<int>& arr) {
//        int fast = -1;
//        int slow = 0;
//        int n = arr.size();
//        while (slow < n)
//        {
//            if (arr[slow] == 0)
//            {
//                fast += 2;
//
//            }
//            else
//            {
//                fast++;
//            }
//            if (fast >= n - 1)
//            {
//                break;
//            }
//            slow++;
//        }
//        if (fast == n)
//        {
//            arr[n - 1] = 0;
//            slow--;
//            fast -= 2;
//        }
//        while (slow >= 0)
//        {
//            if (arr[slow] == 0)
//            {
//                arr[fast--] = arr[slow];
//                arr[fast--] = arr[slow--];
//            }
//            else
//            {
//                arr[fast--] = arr[slow--];
//            }
//        }
//        for (int i = 0; i < n; i++)
//        {
//            cout << arr[i];
//        }
//    }
//};
//
//class Solution {
//public:
//    bool isHappy(int n) {
//        int sum = n;
//        vector<int> vet;
//        while (sum != 1)
//        {
//            int ret = 0;
//            while (sum)
//            {
//                int p = sum % 10;
//                ret += pow(p, 2);
//                sum /= 10;
//            }
//            int q = vet.size();
//            for (int i = 0; i < q; i++)
//            {
//                if (ret == vet[i])
//                {
//                    return false;
//                }
//            }
//            vet.push_back(ret);
//            sum = ret;
//        }
//        return true;
//    }
//};
//
//class Solution {
//public:
//    int maxArea(vector<int>& height) {
//        int left = 0;
//        int right = height.size() - 1;
//        int my_max = min(height[left], height[right]) * (right - left);
//        while (left < right)
//        {
//            if (height[left] < height[right])
//            {
//                left++;
//            }
//            else
//            {
//                right--;
//            }
//            if (my_max < min(height[left], height[right]) * (right - left))
//            {
//                my_max = min(height[left], height[right]) * (right - left);
//            }
//        }
//        return my_max;
//    }
//};
//
//class Solution {
//public:
//    int triangleNumber(vector<int>& nums) {
//        int n = nums.size();
//        if (n < 3)
//        {
//            return 0;
//        }
//        sort(nums.begin(), nums.end());
//        int ret = 0;
//        for (int i = n - 1; i >= 2; i--)
//        {
//            int left = 0;
//            int right = i - 1;
//            while (left < right)
//            {
//                if (nums[left] + nums[right] > nums[i])
//                {
//                    ret += (right - left);
//                    right--;
//                }
//                else
//                {
//                    left++;
//                }
//            }
//        }
//        return ret;
//    }
//};
//
//class Solution {
//public:
//    vector<int> twoSum(vector<int>& nums, int target) {
//        vector<int> ret;
//        int n = nums.size();
//        vector<int> vec = nums;
//        sort(vec.begin(), vec.end());
//        int end = n - 1;
//        int start = 0;
//        while (end > start)
//        {
//            if (vec[start] + vec[end] > target)
//            {
//                end--;
//            }
//            else if (vec[start] + vec[end] < target)
//            {
//                start++;
//            }
//            else
//            {
//                for (int i = 0; i < n; i++)
//                {
//                    if (nums[i] == vec[start] || nums[i] == vec[end])
//                    {
//                        ret.push_back(i);
//                        if (ret.size() == 2)
//                        {
//                            break;
//                        }
//                    }
//                }
//                break;
//            }
//        }
//        return ret;
//    }
//};
//
//class Solution {
//public:
//    vector<int> twoSum(vector<int>& numbers, int target) {
//        int right = numbers.size() - 1;
//        int left = 0;
//        vector<int> ret;
//        while (right > left)
//        {
//            if (numbers[left] + numbers[right] > target)
//            {
//                right--;
//            }
//            else if (numbers[left] + numbers[right] < target)
//            {
//                left++;
//            }
//            else
//            {
//                ret.push_back(left + 1);
//                ret.push_back(right + 1);
//                return ret;
//            }
//        }
//        return ret;
//    }
//};
//
//class Solution {
//public:
//    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
//        vector<int> ret;
//        sort(nums1.begin(), nums1.end());
//        sort(nums2.begin(), nums2.end());
//        int n1 = nums1.size();
//        int n2 = nums2.size();
//        int num = 0;
//        int p = -1;
//        for (int i = 0; i < n1; i++)
//        {
//            for (int k = p + 1; k < n2; k++)
//            {
//                if (nums1[i] == nums2[k])
//                {
//                    p = k;
//                    int z = 0;
//                    for (; z < num; z++)
//                    {
//                        if (ret[z] == nums1[i])
//                        {
//                            break;
//                        }
//                    }
//                    if (z == num)
//                    {
//                        num++;
//                        ret.push_back(nums1[i]);
//                    }
//                    break;
//                }
//            }
//        }
//        return ret;
//    }
//};

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        vector<int> ret;
        int n1 = nums1.size();
        int n2 = nums2.size();
        int r1 = 0;
        int r2 = 0;
        while (r1 < n1)
        {
            while (r1 + 1 < n1 && nums1[r1] == nums1[r1 + 1])
            {
                r1++;
            }
            while (r2 < n2 && nums1[r1] >= nums2[r2])
            {
                if (nums2[r2] == nums1[r1])
                {
                    ret.push_back(nums1[r1]);
                    r2++;
                    break;
                }
                r2++;
            }
            if (r2 == n2)
            {
                break;
            }
            r1++;
        }
        return ret;
    }
};

int main()
{
    vector<int> r1 = { 1,2,1,2 };
    vector<int> r2 = { 2,2 };
    Solution s;
    vector<int> r3 = s.intersection(r1, r2);
    for (int i = 0; i < r3.size(); i++)
    {
        cout << r3[i];
    }
    return 0;
}

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<vector<int>> ret;
        int left = 0;
        while (left < n - 2)
        {
            int right = n - 1;
            int mid = left + 1;
            while (mid < right)
            {
                if (nums[mid] + nums[left] + nums[right] > 0)
                {
                    right--;
                }
                else if (nums[mid] + nums[left] + nums[right] < 0)
                {
                    mid++;
                }
                else
                {
                    vector<int> v;
                    v.push_back(nums[left]);
                    v.push_back(nums[mid]);
                    v.push_back(nums[right]);
                    ret.push_back(v);
                    while (mid < right && (nums[mid] == nums[mid + 1]))
                    {
                        mid++;
                    }
                    mid++;
                }
            }
            left++;
            while (left < n - 2 && (nums[left - 1] == nums[left]))
            {
                left++;
            }
        }
        return ret;
    }
};